Hash算法 1.定义 Hash ：散列，通过关于键值(key)的函数，将数据映射到内存存储中一个位置来访问。这个过程叫做Hash，这个映射函数称做散列函数，存放记录的数组称做散列表(Hash Table),又叫哈希表。 简单地说，它是密码学中的一个重要的函数，一般以

表示。这个函数可以将任意一段数据（一般称这段数据为“消息”）压缩成固定长度的字符串（一般称输出的字符串为“摘要”）。哈希函数需要满足下述条件： 确定性：哈希函数的算法是确定性算法，算法执行过程不引入任何随机量。这意味着相同消息的哈希结果一定相同。 高效性：给定任意一个消息m，可以快速计算

目标抗碰撞性：给定任意一个消息m1,很难找到另一个消息m2，使得

广义抗碰撞性：很难找到两个消息m0不等于m1的情况下，使得

2.优点 先分类，再查找，通过计算，缩小范围，加快查找速度 3.Hash的作用 数字签名：给数据打指纹 比如我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。 密码存储 在用户进行网站登录时，如果服务器直接存储用户密码，则如果服务器被攻击者所攻击，用户的密码就会遭到泄露。最典型的事件就是CSDN的密码明文存储事件了。为了解决这个问题，服务器可以仅存储用户密码的哈希结果。当用户输入登录信息后，服务器端可以计算密码的哈希结果，并与存储的哈希结果进行对比，如果结果相同，则允许用户登录。由于服务器不直接存储用户密码，因此即使服务器被攻击者攻击，用户的密码也不会被泄露。这也是为什么我们在使用【找回密码】功能时，服务器直接请求输入新的密码，而不是把原始密码发送给我们。

4.hash算法的特性 正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。 逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。 输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。 冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。 所以因为他的不可逆性，hash算法常常用来给一些信息加密，因为这种不可逆性，你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件，也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。 5.hash算法（了解） （1）直接定值法：取Key或者Key的某个线性函数值为散列地址。 （2）数字分析法：需要知道Key的集合，并且Key的位数比地址位数多，选择Key数字分布均匀的位。 Hash(Key) 取六位： 列数 ： 1 (2) 3 (4) 5 (6) (7) 8 (9) 10 11 12 (13) key1： 5 2 4 2 7 5 8 5 3 6 5 1 3 key2： 5 4 4 8 7 7 7 5 4 8 9 5 1 key3： 3 1 5 3 7 8 5 4 6 3 5 5 2 key4： 5 3 6 4 3 2 5 4 5 3 2 6 4

其中(2、4、6、7、9、13) 这6列数字无重复，分布较均匀，取此六列作为Hash(Key)的值。 Hash(Key1) :225833 Hash(Key2):487741 Hash(Key3):138562 Hash(Key4):342554

（3）平方取中法：取Key平方值的中间几位作为Hash地址。 （4）折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后 取这几部分的叠加和（舍去进位）作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案. （5）随机数法：伪随机探测再散列。 具体实现：建立一个伪随机数发生器，Hash(Key) = random(Key). 以此伪随机数作为哈希地址。 （6）除留余数法：取关键字被某个除数 p 求余，得到的作为散列地址。 即 H(Key) = Key % p； 6.Hash有哪些流行的算法 目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。 MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。 MD5（RFC 1321）是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以 512 位分组，其输出是 128 位。MD5 比 MD4 复杂，并且计算速度要慢一点，更安全一些。MD5 已被证明不具备”强抗碰撞性”。 SHA （Secure Hash Algorithm）是一个 Hash 函数族，由 NIST（National Institute of Standards and Technology）于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世，它的输出为长度 160 位的 hash 值，因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理，并且模仿了该算法。SHA-1 已被证明不具”强抗碰撞性”。 为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

7、何谓Hash算法的「碰撞」？ 如果两个key通过hash函数处理之后得到的散列值相同，这种情况就叫做散列算法的碰撞（collision）。 现代散列算法所存在的理由就是，它的不可逆性能在较大概率上得到实现，也就是说，发现碰撞的概率很小，这种碰撞能被利用的概率更小。 7.1MD5碰撞案例 import hashlib

a = bytearray.fromhex(“0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef”)

b = bytearray.fromhex(“0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef”)

print(hashlib.md5(a).hexdigest()) print(hashlib.md5(b).hexdigest())

这样的例子还有很多。因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是SHA家族算法，也就是安全散列算法（Secure Hash Algorithm，缩写为SHA）。 7.2 SHA家族算法以及SHA1碰撞 SHA家族算法的种类很多，有SHA0、SHA1、SHA256、SHA384等等，它们的计算方式和计算速度都有差别。其中SHA1是现在用途最广泛的一种算法。包括GitHub在内的众多版本控制工具以及各种云同步服务都是用SHA1来区别文件，很多安全证书或是签名也使用SHA1来保证唯一性。长期以来，人们都认为SHA1是十分安全的，至少大家还没有找到一次碰撞案例。